﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Security.Cryptography;
using System.Drawing;
using System.Drawing.Imaging;

namespace Develore.GDiff
{
	/// <summary>
	/// Represents the Generic Diff Format Specification (GDiff) as described on http://www.w3.org/TR/NOTE-gdiff-19970901.
	/// </summary>
	/// <remarks>
	/// The GDiff is a set of bytes that, when applied to a source stream of bytes, produces another stream of
	/// bytes. This can be thought of as the difference between two versions of a document, for instance.
	/// </remarks>
	public static class GDiff
	{

		private const int DefaultBlockSize = 0x200;



		#region public static byte[] Compute(string source, string target)

		/// <summary>
		/// Computes the GDIFF that represents the difference between the two given strings.
		/// </summary>
		/// <param name="source">The source string.</param>
		/// <param name="target">The target string.</param>
		/// <returns>
		/// Returns the GDIFF as a byte array. When this GDIFF is applied to the <paramref name="source"/>
		/// string, the resulting string is a string that equals <paramref name="target"/>.
		/// </returns>
		public static byte[] Compute(string source, string target)
		{
			return Compute(Encoding.UTF8.GetBytes(source), Encoding.UTF8.GetBytes(target));
		}

		#endregion

		#region public static void Compute(string source, string target, Stream result)

		/// <summary>
		/// Computes the GDIFF that represents the difference between <paramref name="source"/>
		/// and <paramref name="target"/>. The result is written to the given
		/// <paramref name="result"/> stream.
		/// </summary>
		/// <param name="source">The source string.</param>
		/// <param name="target">The target string.</param>
		/// <param name="result">The stream where to store the resulting GDIFF.</param>
		public static void Compute(string source, string target, Stream result)
		{
			byte[] buffer = Compute(source, target);
			result.Write(buffer, 0, buffer.Length);
		}

		#endregion

		#region public static byte[] Compute(byte[] sourceBuffer, byte[] targetBuffer)

		/// <summary>
		/// Computes the GDIFF that represents the difference between the given
		/// byte arrays <paramref name="sourceBuffer"/> and <paramref name="targetBuffer"/>.
		/// </summary>
		/// <param name="sourceBuffer">The source buffer.</param>
		/// <param name="targetBuffer">The target buffer.</param>
		/// <returns>
		/// Returns the GDIFF as a byte array.
		/// </returns>
		public static byte[] Compute(byte[] sourceBuffer, byte[] targetBuffer)
		{
			return Compute(sourceBuffer, targetBuffer, DefaultBlockSize);
		}

		#endregion

		#region public static byte[] Compute(byte[] sourceBuffer, byte[] targetBuffer, int blockSize)

		/// <summary>
		/// Computes the GDIFF that represents the difference between the given
		/// byte arrays <paramref name="sourceBuffer"/> and <paramref name="targetBuffer"/>
		/// using the specified block size.
		/// </summary>
		/// <param name="sourceBuffer">The source buffer.</param>
		/// <param name="targetBuffer">The target buffer.</param>
		/// <param name="blockSize">The block size to use when computing the GDIFF.</param>
		/// <returns>
		/// Returns the GDIFF as a byte array.
		/// </returns>
		public static byte[] Compute(byte[] sourceBuffer, byte[] targetBuffer, int blockSize)
		{
			using (MemoryStream source = new MemoryStream(sourceBuffer))
			{
				source.Position = 0;
				using (MemoryStream target = new MemoryStream(targetBuffer))
				{
					target.Position = 0;

					using (MemoryStream result = new MemoryStream())
					{
						Compute(source, target, result, blockSize);

						result.Position = 0;
						byte[] buffer = new byte[result.Length];
						result.Read(buffer, 0, buffer.Length);

						return buffer;
					}
				}
			}
		}

		#endregion
		
		#region public static void Compute(Stream source, Stream target, Stream result)

		/// <summary>
		/// Computes a GDIFF between <paramref name="source"/> and <paramref name="target"/> that,
		/// when applied to <paramref name="source"/>, produces the <paramref name="target"/>.
		/// </summary>
		/// <param name="source">The source data to compute the GDIFF from.</param>
		/// <param name="target">The target data that you want to get when applying <paramref name="result"/> to <paramref name="source"/>.</param>
		/// <param name="result">The stream the will contain the resulting GDIFF data.</param>
		public static void Compute(Stream source, Stream target, Stream result)
		{
			Compute(source, target, result, DefaultBlockSize);
		}

		#endregion

		#region public static void Compute(Stream source, Stream target, Stream result, int blockSize)

		/// <summary>
		/// Computes a GDIFF between <paramref name="source"/> and <paramref name="target"/> that,
		/// when applied to <paramref name="source"/>, produces the <paramref name="target"/>.
		/// </summary>
		/// <param name="source">The source data to compute the GDIFF from.</param>
		/// <param name="target">The target data that you want to get when applying <paramref name="result"/> to <paramref name="source"/>.</param>
		/// <param name="result">The stream the will contain the resulting GDIFF data.</param>
		/// <param name="blockSize">The block size to use when computing the GDIFF.</param>
		public static void Compute(Stream source, Stream target, Stream result, int blockSize)
		{
			if (null == source)
				throw new ArgumentNullException("source");

			if (null == target)
				throw new ArgumentNullException("target");

			result.Write(new byte[] { 0xd1, 0xff, 0xd1, 0xff, 0x04 }, 0, 5);

			byte[] buf = null;
			StreamSeeker seeker = new StreamSeeker(source, blockSize);

			while (target.Position < target.Length)
			{
				DiffBlock block = GetNextBlock(target, blockSize);

				long? pos = seeker.FindBlockPosition(block);

				if (pos.HasValue)
				{
					if (pos.Value <= ushort.MaxValue && block.Data.Length <= byte.MaxValue)
					{
						// Command 249
						result.WriteByte(249);

						buf = GetBytes((ushort)pos.Value);
						result.Write(buf, 0, buf.Length);

						result.WriteByte((byte)block.Data.Length);
					}
					else if (pos.Value <= ushort.MaxValue && block.Data.Length <= ushort.MaxValue)
					{
						// Command 250
						result.WriteByte(250);

						buf = GetBytes((ushort)pos.Value);
						result.Write(buf, 0, buf.Length);

						buf = GetBytes((ushort)block.Data.Length);
						result.Write(buf, 0, buf.Length);
					}
					else if(pos.Value <= ushort.MaxValue && block.Data.Length <= int.MaxValue)
					{
						// Command 251
						result.WriteByte(251);

						buf = GetBytes((ushort)pos.Value);
						result.Write(buf, 0, buf.Length);

						buf = GetBytes((int)block.Data.Length);
						result.Write(buf, 0, buf.Length);
					}
					else if (pos.Value <= int.MaxValue && block.Data.Length <= byte.MaxValue)
					{
						// Command 252
						result.WriteByte(252);

						buf = GetBytes((int)pos.Value);
						result.Write(buf, 0, buf.Length);

						result.WriteByte((byte)block.Data.Length);
					}
					else if (pos.Value <= int.MaxValue && block.Data.Length <= ushort.MaxValue)
					{
						// Command 253
						result.WriteByte(253);

						buf = GetBytes((int)pos.Value);
						result.Write(buf, 0, buf.Length);

						buf = GetBytes((ushort)block.Data.Length);
						result.Write(buf, 0, buf.Length);
					}
					else if (pos.Value <= int.MaxValue && block.Data.Length < int.MaxValue)
					{
						// Command 254
						result.WriteByte(254);

						buf = GetBytes((int)pos.Value);
						result.Write(buf, 0, buf.Length);

						buf = GetBytes((int)block.Data.Length);
						result.Write(buf, 0, buf.Length);
					}
					else
					{
						// Command 255
						result.WriteByte(255);

						buf = GetBytes(pos.Value);
						result.Write(buf, 0, buf.Length);

						buf = GetBytes((int)block.Data.Length);
						result.Write(buf, 0, buf.Length);
					}
				}
				else
				{
					result.WriteByte(248);

					buf = GetBytes((int)block.Data.Length);
					result.Write(buf, 0, buf.Length);
					result.Write(block.Data, 0, block.Data.Length);
				}
			}

			result.WriteByte(0);
		}

		#endregion
		
		#region public static void Compute(FileInfo sourceFile, FileInfo targetFile, FileInfo resultFile)

		/// <summary>
		/// Computes a GDIFF between the files <paramref name="sourceFile"/> and
		/// <paramref name="targetFile"/> that, when applied to the file specified in
		/// <paramref name="sourceFile"/>, produces the file specified in <paramref name="targetFile"/>.
		/// </summary>
		/// <param name="sourceFile">The source file to compute the GDIFF from.</param>
		/// <param name="targetFile">The target file that should be produced when applying the resulting GDIFF to the file specified in <paramref name="sourceFile"/>.</param>
		/// <param name="resultFile">The file to store the resulting GDIFF in.</param>
		public static void Compute(FileInfo sourceFile, FileInfo targetFile, FileInfo resultFile)
		{
			using (FileStream source = new FileStream(sourceFile.FullName, FileMode.Open, FileAccess.Read))
			{
				using (FileStream target = new FileStream(targetFile.FullName, FileMode.Open, FileAccess.Read))
				{
					using (FileStream result = new FileStream(resultFile.FullName, FileMode.CreateNew, FileAccess.Write))
					{
						GDiff.Compute(source, target, result);
					}
				}
			}
		}

		#endregion



		#region public static string Apply(byte[] gdiff, string source)

		/// <summary>
		/// Applies the given GDIFF to the given string and produces a new string.
		/// </summary>
		/// <param name="gdiff">The GDIFF to apply to the given string.</param>
		/// <param name="source">The string to apply the given GDIFF to.</param>
		/// <returns>Returns a new string.</returns>
		/// <remarks>
		/// The GDIFF for this method can be obtained by calling the <see cref="Compute(string, string)"/>
		/// method.
		/// </remarks>
		public static string Apply(byte[] gdiff, string source)
		{
			using (MemoryStream sourceStream = new MemoryStream(Encoding.UTF8.GetBytes(source)))
			{
				sourceStream.Position = 0;
				using (MemoryStream targetStream = new MemoryStream())
				{
					using (MemoryStream gdiffStream = new MemoryStream(gdiff))
					{
						gdiffStream.Position = 0;
						Apply(gdiffStream, sourceStream, targetStream);
					}

					targetStream.Position = 0;
					byte[] buffer = new byte[targetStream.Length];
					targetStream.Read(buffer, 0, buffer.Length);

					return Encoding.UTF8.GetString(buffer);
				}
			}
		}

		#endregion

		#region public static string Apply(Stream gdiff, string source)

		/// <summary>
		/// Applies the given GDIFF to the given string and produces a new string.
		/// </summary>
		/// <param name="gdiff">The GDIFF to apply to the given string.</param>
		/// <param name="source">The string to apply the GDIFF to.</param>
		/// <returns>Returns a new string.</returns>
		/// <remarks>
		/// The GDIFF for this method can be obtained by calling the <see cref="Compute(string, string, Stream)"/>
		/// method.
		/// </remarks>
		public static string Apply(Stream gdiff, string source)
		{
			using (MemoryStream sourceStream = new MemoryStream(Encoding.UTF8.GetBytes(source)))
			{
				sourceStream.Position = 0;

				using (MemoryStream targetStream = new MemoryStream())
				{
					Apply(gdiff, sourceStream, targetStream);

					targetStream.Position = 0;

					byte[] buffer = new byte[targetStream.Length];
					targetStream.Read(buffer, 0, buffer.Length);

					return Encoding.UTF8.GetString(buffer);
				}
			}
		}

		#endregion

		#region public static byte[] Apply(byte[] gdiff, byte[] source)

		/// <summary>
		/// Applies the given GDIFF to the given byte array and produces a new byte array.
		/// </summary>
		/// <param name="gdiff">The GDIFF to apply to the given byte array.</param>
		/// <param name="source">The byte array to apply the given GDIFF to.</param>
		/// <returns>Returns a new byte array.</returns>
		/// <remarks>
		/// The GDIFF for this method can be obtained by calling the
		/// <see cref="Compute(byte[], byte[])"/> or <see cref="Compute(byte[], byte[], int)"/> method.
		/// </remarks>
		public static byte[] Apply(byte[] gdiff, byte[] source)
		{
			using (MemoryStream sourceStream = new MemoryStream(source))
			{
				sourceStream.Position = 0;
				using (MemoryStream targetStream = new MemoryStream())
				{
					using (MemoryStream gdiffStream = new MemoryStream(gdiff))
					{
						gdiffStream.Position = 0;
						Apply(gdiffStream, sourceStream, targetStream);
					}

					targetStream.Position = 0;
					byte[] buffer = new byte[targetStream.Length];
					targetStream.Read(buffer, 0, buffer.Length);

					return buffer;
				}
			}
		}

		#endregion
		
		#region public static void Apply(FileInfo gdiffFile, FileInfo sourceFile, FileInfo targetFile)

		/// <summary>
		/// Applies the GDIFF stored in the given file to the file given in <paramref name="sourceFile"/>
		/// and writes the results to the file specified in <paramref name="targetFile"/>.
		/// </summary>
		/// <param name="gdiffFile">The file containing the GDIFF to apply to <paramref name="sourceFile"/>.</param>
		/// <param name="sourceFile">The file to apply the given GDIFF to.</param>
		/// <param name="targetFile">The file to write the result to.</param>
		/// <remarks>
		/// The GDIFF for this method can be produced by calling the
		/// <see cref="Compute(FileInfo, FileInfo, FileInfo)"/> method.
		/// </remarks>
		public static void Apply(FileInfo gdiffFile, FileInfo sourceFile, FileInfo targetFile)
		{
			using (FileStream gdiff = new FileStream(gdiffFile.FullName, FileMode.Open, FileAccess.Read))
			{
				using (FileStream source = new FileStream(sourceFile.FullName, FileMode.Open, FileAccess.Read))
				{
					using (FileStream target = new FileStream(targetFile.FullName, FileMode.CreateNew, FileAccess.Write))
					{
						Apply(gdiff, source, target);
					}
				}
			}
		}

		#endregion

		#region public static void Apply(Stream gdiff, Stream source, Stream target)

		/// <summary>
		/// Applies the GDIFF stored in <paramref name="gdiff"/> to the data stored in
		/// <paramref name="source"/> and writes the result to the stream specified
		/// in <paramref name="target"/>.
		/// </summary>
		/// <param name="gdiff">The stream containing the GDIFF to apply to the data stored in <paramref name="source"/>.</param>
		/// <param name="source">The stream containing the data to apply the given GDIFF to.</param>
		/// <param name="target">The stream to write the result to.</param>
		/// <remarks>
		/// The GDIFF for this method can be produced by calling the
		/// <see cref="Compute(Stream, Stream, Stream)"/> or <see cref="Compute(Stream, Stream, Stream, int)"/> method.
		/// </remarks>
		public static void Apply(Stream gdiff, Stream source, Stream target)
		{
			if (gdiff.Position > 0)
				gdiff.Position = 0;

			byte[] buffer = new byte[5];
			gdiff.Read(buffer, 0, buffer.Length);
			if (buffer[0] != 0xd1 || buffer[1] != 0xff || buffer[2] != 0xd1 || buffer[3] != 0xff || buffer[4] != 0x04)
				throw new InvalidDataException("The given GDIFF is not valid.");

			byte command = (byte)gdiff.ReadByte();
			long pos = 0;
			int len = 0;

			while (gdiff.Position < gdiff.Length - 1 && command > 0)
			{

				// 1 - 248 are DATA commands. 249 to 255 are copy commands.
				switch (command)
				{

					#region COPY commands

					case 249: // COPY ushort, ubyte (position, length)
						pos = (long)ReadUInt16(gdiff);
						len = (byte)gdiff.ReadByte();

						break;

					case 250: // COPY ushort, ushort (position, length)
						pos = (long)ReadUInt16(gdiff);
						len = (int)ReadUInt16(gdiff);

						break;

					case 251: // COPY ushort, int (position, length)
						pos = (long)ReadUInt16(gdiff);
						len = ReadInt32(gdiff);

						break;

					case 252: // COPY int, ubyte (position, length)
						pos = (long)ReadInt32(gdiff);
						len = gdiff.ReadByte();

						break;

					case 253: // COPY int, ushort (position, length)
						pos = (long)ReadInt32(gdiff);
						len = (int)ReadUInt16(gdiff);

						break;

					case 254: // COPY int, int (position, length)
						pos = (long)ReadInt32(gdiff);
						len = ReadInt32(gdiff);

						break;

					case 255: // COPY long, int (position, length)
						pos = ReadInt64(gdiff);
						len = ReadInt32(gdiff);

						break;

					#endregion

					#region DATA commands

					default:
						// DATA commands

						if (command < 247)
						{
							len = command;
						}
						else if (command == 247)
						{
							len = ReadUInt16(gdiff);
						}
						else if (command == 248)
						{
							len = ReadInt32(gdiff);
						}

						buffer = new byte[len];
						gdiff.Read(buffer, 0, buffer.Length);
						target.Write(buffer, 0, buffer.Length);
						break;

					#endregion

				}

				if (command >= 249)
				{
					source.Position = pos;
					buffer = new byte[len];
					source.Read(buffer, 0, buffer.Length);
					target.Write(buffer, 0, buffer.Length);
				}

				command = (byte)gdiff.ReadByte();
			}

		}

		#endregion



		#region private static bool BuffersEqual(byte[] buffer1, byte[] buffer2)

		/// <summary>
		/// Compares the two buffers and returns true if they are equal.
		/// </summary>
		/// <param name="buffer1">The first buffer.</param>
		/// <param name="buffer2">The second buffer.</param>
		private static bool BuffersEqual(byte[] buffer1, byte[] buffer2)
		{
			if (null == buffer1 && null == buffer2)
				return true;

			if (null == buffer1 || null == buffer2)
				return false;

			if (buffer1.Length != buffer2.Length)
				return false;

			using (MD5 hash = MD5.Create())
			{
				hash.ComputeHash(buffer1);
				string hash1 = BitConverter.ToString(hash.Hash);

				hash.ComputeHash(buffer2);
				string hash2 = BitConverter.ToString(hash.Hash);

				return string.Equals(hash1, hash2);
			}
		}

		#endregion

		#region private static byte[] GetBytes(int value)

		/// <summary>
		/// Converts the given integer to a series of bytes that are
		/// stored in big endian byte order.
		/// </summary>
		/// <param name="value">The integer to convert.</param>
		private static byte[] GetBytes(int value)
		{
			return GetBytes(BitConverter.GetBytes(value));
		}

		#endregion

		#region private static byte[] GetBytes(uint value)

		/// <summary>
		/// Converts the given unsigned integer to a series of bytes that are
		/// stored in big endian byte order.
		/// </summary>
		/// <param name="value">The unsigned integer to convert.</param>
		private static byte[] GetBytes(uint value)
		{
			return GetBytes(BitConverter.GetBytes(value));
		}

		#endregion

		#region private static byte[] GetBytes(long value)

		/// <summary>
		/// Converts the given long to a series of bytes that are
		/// stored in big endian byte order.
		/// </summary>
		/// <param name="value">The long to convert.</param>
		private static byte[] GetBytes(long value)
		{
			return GetBytes(BitConverter.GetBytes(value));
		}

		#endregion

		#region private static byte[] GetBytes(ushort value)

		/// <summary>
		/// Converts the given unsigned short to a series of bytes that are
		/// stored in big endian byte order.
		/// </summary>
		/// <param name="value">The unsigned short to convert.</param>
		private static byte[] GetBytes(ushort value)
		{
			return GetBytes(BitConverter.GetBytes(value));
		}

		#endregion

		#region private static byte[] GetBytes(byte[] buffer)

		/// <summary>
		/// Reverses the given byte array if the current system is storing
		/// bytes in little endian byte order. If the current system stores
		/// bytes in big endian byte order, the given byte array is returned
		/// as is.
		/// </summary>
		/// <param name="buffer">The byte array to manipulate.</param>
		private static byte[] GetBytes(byte[] buffer)
		{
			if (BitConverter.IsLittleEndian)
				return buffer.Reverse().ToArray();

			return buffer;
		}

		#endregion

		#region private static DiffBlock GetNextBlock(Stream stream, int blockSize)

		/// <summary>
		/// Returns the next block from the given stream starting from the stream's
		/// current location.
		/// </summary>
		/// <param name="stream">The stream to get the next block from.</param>
		/// <param name="blockSize">The size of the block to return.</param>
		/// <returns></returns>
		private static DiffBlock GetNextBlock(Stream stream, int blockSize)
		{

			if (null == stream)
				throw new ArgumentNullException("stream");

			if (blockSize < 1)
				throw new ArgumentException("Block size cannot be less than 1.", "blockSize");

			DiffBlock block = new DiffBlock();
			block.SourceIndex = stream.Position;

			byte[] buffer = new byte[Math.Min(blockSize, stream.Length - stream.Position)];
			stream.Read(buffer, 0, buffer.Length);

			block.Data = buffer;

			using (Adler32 hash = new Adler32(buffer))
			{
				block.WeakHash = hash.Hash;
			}

			using (MD5 hash = MD5.Create())
			{
				hash.ComputeHash(buffer);
				block.StrongHash = hash.Hash;
			}

			return block;
		}

		#endregion

		#region private static int ReadInt32(Stream stream)

		/// <summary>
		/// Reads the next 4 bytes from the given stream and converts them to
		/// and integer.
		/// </summary>
		/// <remarks>
		/// This method assumes that the bytes are stored in big endian byte
		/// order in the given stream.
		/// </remarks>
		/// <param name="stream">The stream to read from.</param>
		private static int ReadInt32(Stream stream)
		{
			byte[] buffer = new byte[4];
			stream.Read(buffer, 0, buffer.Length);
			return ToInt32(buffer);
		}

		#endregion

		#region private static long ReadInt64(Stream stream)

		/// <summary>
		/// Reads the next 8 bytes from the given stream and converts them to
		/// a long.
		/// </summary>
		/// <remarks>
		/// This method assumes that the bytes are stored in big endian byte
		/// order in the given stream.
		/// </remarks>
		/// <param name="stream">The stream to read from.</param>
		private static long ReadInt64(Stream stream)
		{
			byte[] buffer = new byte[8];
			stream.Read(buffer, 0, buffer.Length);
			return ToInt64(buffer);
		}

		#endregion

		#region private static ushort ReadUInt16(Stream stream)

		/// <summary>
		/// Reads the next 2 bytes from the given stream and converts them to
		/// an unsigned short.
		/// </summary>
		/// <remarks>
		/// This method assumes that the bytes are stored in big endian byte
		/// order in the given stream.
		/// </remarks>
		/// <param name="stream">The stream to read from.</param>
		private static ushort ReadUInt16(Stream stream)
		{
			byte[] buffer = new byte[2];
			stream.Read(buffer, 0, buffer.Length);
			return ToUInt16(buffer);
		}

		#endregion

		#region private static int ToInt32(byte[] bytes)

		/// <summary>
		/// Converts the given bytes to an interger.
		/// </summary>
		/// <remarks>
		/// This method assumes that the given bytes are stored in big endian byte order.
		/// </remarks>
		/// <param name="bytes">The bytes to convert.</param>
		private static int ToInt32(byte[] bytes)
		{
			return BitConverter.ToInt32(GetBytes(bytes), 0);
		}

		#endregion

		#region private static long ToInt64(byte[] bytes)

		/// <summary>
		/// Converts the given bytes to a long.
		/// </summary>
		/// <remarks>
		/// This method assumes that the given bytes are stored in big endian byte order.
		/// </remarks>
		/// <param name="bytes">The bytes to convert.</param>
		private static long ToInt64(byte[] bytes)
		{
			return BitConverter.ToInt64(GetBytes(bytes), 0);
		}

		#endregion

		#region private static ushort ToUInt16(byte[] bytes)

		/// <summary>
		/// Converts the given bytes to an unsigned short.
		/// </summary>
		/// <remarks>
		/// This method assumes that the given bytes are stored in big endian byte order.
		/// </remarks>
		/// <param name="bytes">The bytes to convert.</param>
		private static ushort ToUInt16(byte[] bytes)
		{
			return BitConverter.ToUInt16(GetBytes(bytes), 0);
		}

		#endregion

	}
}
